import java.util.*;

/**
 * Created by L.jp
 * Description:nums1中数字x的 下一个更大元素 是指x在nums2 中对应位置 右侧 的 第一个 比x大的元素。
 *
 * 给你两个 没有重复元素 的数组nums1 和nums2 ，下标从 0 开始计数，其中nums1nums2的子集。
 *
 * 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
 *
 * 返回一个长度为nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。

 * User: 86189
 * Date: 2022-02-14
 * Time: 9:44
 */
/*  思路：凡是遇到下一个更大元素的字样就是用单调栈
        什么叫做单调栈？
        从名字上就听的出来，单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈
单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

对于单调栈，我们解决问题最好借助Deque接口的ArrayDeque接口，因为Java 提供了 Deuqe。Deque 是继承自 Queue，而 Stack 是继承自 Vector。Java 中的 Deuqe，即“double
ended queue”的缩写，是 Java 中的双端队列集合类型。Deque 具备普通队列 FIFO 的功能，同时它也具备了
Stack 的 LIFO 功能，并且保留了 push 和 pop 函数，所以使用起来应该是一点障碍都没有。

ArrayDeque 是 Deque 接口的一种具体实现，是依赖于可变数组来实现的。ArrayDeque 没有容量限制，可根
据需求自动进行扩容。ArrayDeque 可以作为栈来使用，效率要高于 Stack。ArrayDeque 也可以作为队列来使
用，效率相较于基于双向链表的 LinkedList 也要更好一些。注意，ArrayDeque 不支持为 null 的元素。

那么单调栈的原理是什么呢？
比如：
对于是维护单调递增栈还是单调递减栈，我们需要根据题目中数据元素的排序趋势，或者根据题目要求
比如我们需要依次将数组 [1,3,4,5,2,9,6] 压入单调栈。
1. 首先压入 1，此时的栈为：[1]
2. 继续压入 3，此时的栈为：[1,3]
3. 继续压入 4，此时的栈为：[1,3,4]
4. 继续压入 5，此时的栈为：[1,3,4,5]
5. 如果继续压入 2，此时的栈为：[1,3,4,5,2] 不满足单调递减栈的特性， 因此需要调整。如何调整？由于栈只有
pop 操作，因此我们只好不断 pop，直到满足单调递减为止。
6. 上面其实我们并没有压入 2，而是先 pop，pop 到压入 2 依然可以保持单调递减再 压入 2，此时的栈为：[1,2]
7. 继续压入 9，此时的栈为：[1,2,9]
8. 如果继续压入 6，则不满足单调递减栈的特性， 我们故技重施，不断 pop，直到满足单调递减为止。此时的栈
为：[1,2,6]

而对于这个求下一个更大元素的问题，我们就刚好可以维护一个单调递减栈，由于数组里面的大小顺序不一致，所以我们维护一个单调递减栈的
时候需要不断维护使得这个栈一直是单调递减，所以我们可以从数组后面开始遍历元素，使得栈内保存的就是下一个元素，而当前元素就是
上一个元素，而如果从数组前面开始遍历的话，那么当前元素就是下一个元素，栈顶的元素就是上一个元素，从后往前或者从前往后都可以
主要是要维护一个单调递减栈

*
* */
public class Solution {
    //对于这个问题，我们可以借助一个单调栈来保存下一个更大元素，然后还可以借助哈希表来存储每一个元素与其下一个更大元素，形成映射关系
    //因为要在nums2数组里找nums1数组元素的下一个更大元素，所以我们就可以直接对nums2数组维护一个单调栈与哈希表，保存下一个更大元素
    //然后遍历num1数组，直接用哈希表的get方法得到对应的值，存到一个新的数组里面，最后返回新数组
    //对于单调栈，一定需要弹出元素
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //如果使用stack的话，那么代码如下：
       /*
       Stack<Integer> stack=new Stack<>();
        Map<Integer,Integer> map=new HashMap<>();
        int[] ret= new int[nums1.length];//存储nums1数组元素对应的下一个更大元素
        //对nums2数组正序遍历，那么当前元素就是下一个元素，栈顶的就是上一个元素
        for(int i = 0;i<nums2.length;i++){
            //栈顶代表上一个元素
            while(!stack.isEmpty() && stack.peek()<nums2[i]){
                //说明有下一个更大元素，那么就出栈元素，然后把当前元素和栈顶元素入哈希表保存
                map.put(stack.pop(),nums2[i]);

            }
            //如果栈为空或者是栈顶元素大于当前元素就入栈
            stack.push(nums2[i]);
        }
        //遍历完了nums2就表示存完了，接下来直接读取了
        for(int i = 0;i<nums1.length;i++){
            //有下一个更大元素就获取，没有就设置为-1
            ret[i]=map.getOrDefault(nums2[i],-1);
        }
        return ret;*/

        //如果用ArrayDeque的话，代码如下：
        Deque<Integer> deque=new ArrayDeque<>();
        Map<Integer, Integer> map=new HashMap<>();
        //正序遍历nums2
        for(int num:nums2){
            //peekLast代表获取栈顶元素，栈顶元素小于当前元素，表示有下一个更大元素
            while(!deque.isEmpty() && deque.peekLast()<num){
                map.put(deque.pollLast(),num); //对于符合要求的元素，一定要弹出上一个元素才能做下一步判断
                // 如果不弹出元素，那么就一直在循环里面，判断不了下一步元素，pollLast弹出栈顶元素，跟peekLast对应
            }
            //如果栈顶大于当前元素，表示没有下一个更大元素，先入栈，之后再用哈希表保存
            deque.addLast(num); //入栈顶
        }
        int[] ret=new int[nums1.length];
        for(int i = 0;i<nums1.length; i++){
            ret[i]=map.getOrDefault(nums1[i],-1);
        }
        return ret;

        //如果是逆向遍历，那么栈顶就代表下一个更大元素，当前元素就是上一个元素
//        for(int i = nums2.length-1;i>=0;i--){
//            //如果栈不为空，而且下一个元素比上一个元素小，那么就出栈，保证栈顶元素就是下一个更大元素
//            while(!deque.isEmpty() && deque.peekLast()<nums2[i]){
//                deque.pollLast();
//            }
//            //如果栈为空或者下一个元素比上一个元素大，也就是栈顶元素大于当前元素，那么就把当前元素和栈顶元素入栈，为空的话就入-1
//            map.put(nums2[i],deque.isEmpty() ? -1 : deque.peekLast());
//            //然后再把当前元素入栈，以便下一步判断
//            deque.addLast(nums2[i]);
//        }
//        int[] ret=new int[nums1.length];
//        for(int i = 0;i<nums1.length; i++){
//            ret[i]=map.get(nums1[i]);
//        }
//        return  ret;
    }
}
